{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Intervals Between Identical Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getDistances"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #相同元素的间隔之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、由 <code>n</code> 个整数组成的数组 <code>arr</code> 。</p>\n",
    "\n",
    "<p><code>arr</code> 中两个元素的 <strong>间隔</strong> 定义为它们下标之间的 <strong>绝对差</strong> 。更正式地，<code>arr[i]</code> 和 <code>arr[j]</code> 之间的间隔是 <code>|i - j|</code> 。</p>\n",
    "\n",
    "<p>返回一个长度为 <code>n</code> 的数组&nbsp;<code>intervals</code> ，其中 <code>intervals[i]</code> 是<em> </em><code>arr[i]</code><em> </em>和<em> </em><code>arr</code><em> </em>中每个相同元素（与 <code>arr[i]</code> 的值相同）的 <strong>间隔之和</strong> <em>。</em></p>\n",
    "\n",
    "<p><strong>注意：</strong><code>|x|</code> 是 <code>x</code> 的绝对值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,1,3,1,2,3,3]\n",
    "<strong>输出：</strong>[4,2,7,2,4,4,5]\n",
    "<strong>解释：</strong>\n",
    "- 下标 0 ：另一个 2 在下标 4 ，|0 - 4| = 4\n",
    "- 下标 1 ：另一个 1 在下标 3 ，|1 - 3| = 2\n",
    "- 下标 2 ：另两个 3 在下标 5 和 6 ，|2 - 5| + |2 - 6| = 7\n",
    "- 下标 3 ：另一个 1 在下标 1 ，|3 - 1| = 2\n",
    "- 下标 4 ：另一个 2 在下标 0 ，|4 - 0| = 4\n",
    "- 下标 5 ：另两个 3 在下标 2 和 6 ，|5 - 2| + |5 - 6| = 4\n",
    "- 下标 6 ：另两个 3 在下标 2 和 5 ，|6 - 2| + |6 - 5| = 5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [10,5,10,10]\n",
    "<strong>输出：</strong>[5,0,3,4]\n",
    "<strong>解释：</strong>\n",
    "- 下标 0 ：另两个 10 在下标 2 和 3 ，|0 - 2| + |0 - 3| = 5\n",
    "- 下标 1 ：只有这一个 5 在数组中，所以到相同元素的间隔之和是 0\n",
    "- 下标 2 ：另两个 10 在下标 0 和 3 ，|2 - 0| + |2 - 3| = 3\n",
    "- 下标 3 ：另两个 10 在下标 0 和 2 ，|3 - 0| + |3 - 2| = 4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == arr.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [intervals-between-identical-elements](https://leetcode.cn/problems/intervals-between-identical-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [intervals-between-identical-elements](https://leetcode.cn/problems/intervals-between-identical-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3,1,2,3,3]', '[10,5,10,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        d = defaultdict(list)\n",
    "        for i, v in enumerate(arr):\n",
    "            d[v].append(i)\n",
    "        res = [0] * len(arr)\n",
    "\n",
    "        for v in d:\n",
    "            indexes = d[v]\n",
    "            pre = [0] * (len(indexes) + 1)\n",
    "            for i in range(len(indexes)):\n",
    "                pre[i+1] = pre[i] + indexes[i]\n",
    "            for i, value in enumerate(indexes):\n",
    "                res[value] = value * (i+1) - pre[i+1] + (pre[len(indexes)] - pre[i] - value * (len(indexes) - i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        dct={}\n",
    "        res=[0]*len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            dct.setdefault(arr[i],(0,0))\n",
    "            dct[arr[i]]=(dct[arr[i]][0]+i,dct[arr[i]][1]+1)\n",
    "            res[i]+=i*dct[arr[i]][1]-dct[arr[i]][0]\n",
    "        dct={}\n",
    "        for j in range(len(arr)-1,-1,-1):\n",
    "            dct.setdefault(arr[j],(0,0))\n",
    "            dct[arr[j]]=(dct[arr[j]][0]+j,dct[arr[j]][1]+1)\n",
    "            res[j]+=dct[arr[j]][0]-j*dct[arr[j]][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        num_dict = {}\n",
    "        ans = [0] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if num_dict.get(arr[i]) is None:\n",
    "                num_dict[arr[i]] = [i]\n",
    "            else:\n",
    "                num_dict[arr[i]].append(i)\n",
    "        \n",
    "        for _, lst in num_dict.items():\n",
    "            l, r, n = 0, sum(lst), len(lst)\n",
    "            for i in range(n):\n",
    "                r -= lst[i]\n",
    "                ans[lst[i]] = (i - (len(lst) - 1 - i)) * lst[i] + r - l\n",
    "                l += lst[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        intervals = [0]*len(arr)\n",
    "        cnt = dict()\n",
    "        for i, val in enumerate(arr):\n",
    "            if val in cnt:\n",
    "                cnt[val].append(i)\n",
    "            else:\n",
    "                cnt[val] = [i]\n",
    "        for key in cnt:\n",
    "            t = sum(cnt[key]) - len(cnt[key])*cnt[key][0]\n",
    "            n = -len(cnt[key])+1\n",
    "            intervals[cnt[key][0]] = t\n",
    "            for j in range(1,len(cnt[key])):\n",
    "                n+=2\n",
    "                delta = cnt[key][j] - cnt[key][j-1]\n",
    "                t+=delta*(n-1)\n",
    "                intervals[cnt[key][j]] = (t)\n",
    "        return intervals\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = [0] * n   # 每个元素与相同元素间隔之和\n",
    "        total = defaultdict(int)   # 每个数值出现下标之和\n",
    "        cnt = defaultdict(int)   # 每个数值出现次数\n",
    "        # 正向遍历并更新两个哈希表以及间隔之和数组\n",
    "        for i in range(n):\n",
    "            val = arr[i]\n",
    "            if val in cnt:\n",
    "                res[i] += i * cnt[val] - total[val]\n",
    "            total[val] += i\n",
    "            cnt[val] += 1\n",
    "        # 清空哈希表，反向遍历并更新两个哈希表以及间隔之和数组\n",
    "        total.clear()\n",
    "        cnt.clear()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            val = arr[i]\n",
    "            if val in cnt:\n",
    "                res[i] += total[val] - i * cnt[val] \n",
    "            total[val] += i\n",
    "            cnt[val] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        intervals = [0]*len(arr)\n",
    "        cnt = dict()\n",
    "        for i, val in enumerate(arr):\n",
    "            if val in cnt:\n",
    "                cnt[val].append(i)\n",
    "            else:\n",
    "                cnt[val] = [i]\n",
    "        for key in cnt:\n",
    "            t = sum(cnt[key]) - len(cnt[key])*cnt[key][0]\n",
    "            n = -len(cnt[key])\n",
    "            intervals[cnt[key][0]] = t\n",
    "            for j in range(1,len(cnt[key])):\n",
    "                n+=2\n",
    "                delta = cnt[key][j] - cnt[key][j-1]\n",
    "                t+=delta*n\n",
    "                intervals[cnt[key][j]] = (t)\n",
    "        return intervals\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def func(self,L,res):\n",
    "        qianzhui = [0]*len(L)\n",
    "        qianzhui[0] = L[0]\n",
    "        for i in range(1,len(L)):\n",
    "            qianzhui[i] = qianzhui[i-1]+L[i]\n",
    "        for i in range(len(L)):\n",
    "            left = qianzhui[i]-L[i]*(i+1)\n",
    "            right = qianzhui[-1]-qianzhui[i]-L[i]*(len(L)-i-1)\n",
    "            res[L[i]] = abs(left)+abs(right)\n",
    "        \n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        helpdic = {}\n",
    "        res = [0]*len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in helpdic:\n",
    "                helpdic[arr[i]].append(i)\n",
    "            else:\n",
    "                helpdic.update({arr[i]: [i]})\n",
    "        for i in range(len(arr)):\n",
    "            try: \n",
    "                if helpdic[arr[i]]:\n",
    "                    self.func(helpdic[arr[i]],res)\n",
    "                    del helpdic[arr[i]]\n",
    "            except:continue\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        intervals = [0]*len(arr)\n",
    "        cnt = dict()\n",
    "        for i, val in enumerate(arr):\n",
    "            if val in cnt:\n",
    "                cnt[val].append(i)\n",
    "            else:\n",
    "                cnt[val] = [i]\n",
    "        for key in cnt:\n",
    "            l,r = 0,sum(cnt[key]) - len(cnt[key])*cnt[key][0]\n",
    "            ln,rn = 0,len(cnt[key])-1\n",
    "            intervals[cnt[key][0]] = r\n",
    "            for j in range(1,len(cnt[key])):\n",
    "                ln+=1\n",
    "                rn-=1\n",
    "                delta = cnt[key][j] - cnt[key][j-1]\n",
    "                l+=delta*ln\n",
    "                r-=delta*(rn+1)\n",
    "                intervals[cnt[key][j]] = (l+r)\n",
    "        return intervals\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        indexs = {}\n",
    "        for i, val in enumerate(arr):\n",
    "            if val in indexs:\n",
    "                indexs[val].append(i)\n",
    "            else:\n",
    "                indexs[val] = [i]\n",
    "        \n",
    "        res = [0] * n\n",
    "\n",
    "        for key, index_list in indexs.items():\n",
    "            n_ = len(index_list)\n",
    "            pre_num = 0\n",
    "            pre_sum = 0\n",
    "            sum_ = sum(index_list)\n",
    "            for index in index_list:\n",
    "                after_num = n_ - pre_num - 1\n",
    "                res[index] = index * pre_num - pre_sum + sum_ - pre_sum - index - index * after_num\n",
    "\n",
    "\n",
    "                pre_num += 1\n",
    "                pre_sum += index\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        mp = {}\n",
    "        n = len(arr)\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            if x in mp:\n",
    "                ans[i] = mp[x][0] * i - mp[x][1]\n",
    "                mp[x][0] += 1\n",
    "                mp[x][1] += i\n",
    "            else:\n",
    "                mp[x] = [1, i]\n",
    "        mp = {}\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = arr[i]\n",
    "            if x in mp:\n",
    "                ans[i] += mp[x][1] - mp[x][0] * i\n",
    "                mp[x][0] += 1\n",
    "                mp[x][1] += i\n",
    "            else:\n",
    "                mp[x] = [1, i]\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        \n",
    "        interval=[0]*len(arr)\n",
    "        total=defaultdict(int)\n",
    "        count=defaultdict(int)\n",
    "        print(total)\n",
    "        print(count)\n",
    "        for i in range(len(arr)):\n",
    "            val=arr[i]\n",
    "            if val in count:\n",
    "                interval[i]+=i*count[val]-total[val]\n",
    "            total[val]+=i\n",
    "            count[val]+=1\n",
    "        print(total)\n",
    "        print(count)\n",
    "        print(interval)\n",
    "        total.clear()\n",
    "        count.clear()\n",
    "        for i in range(len(arr)-1,-1,-1):\n",
    "            val=arr[i]\n",
    "            if val in count:\n",
    "                interval[i]+=total[val]-i*count[val]\n",
    "            total[val]+=i\n",
    "            count[val]+=1\n",
    "        return interval\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    [1, 2, 4, 6, 9]\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        position_recorder = dict()\n",
    "        for index, value in enumerate(arr):\n",
    "            if value in position_recorder:\n",
    "                position_recorder[value].append(index)\n",
    "            else:\n",
    "                position_recorder[value] = [index]\n",
    "        result = [0] * len(arr)\n",
    "        for index_arr in position_recorder.values():\n",
    "            left_value = 0\n",
    "            right_value = sum(index_arr[1:])\n",
    "            arr_length = len(index_arr)\n",
    "            for index, value in enumerate(index_arr):\n",
    "                if index != 0:\n",
    "                    left_value += index_arr[index - 1]\n",
    "                    right_value -= value\n",
    "                result[value] = right_value - left_value - value * (arr_length - index - 1) + value * index\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        d = {}\n",
    "        for idx, num in enumerate(arr):\n",
    "            if num in d.keys():\n",
    "                d[num].append(idx)\n",
    "            else:\n",
    "                d[num] = [idx]\n",
    "        res = [0] * len(arr)\n",
    "        for num, l in d.items():\n",
    "            s = sum([n - l[0] for n in l])\n",
    "            res[l[0]] = s\n",
    "            for i in range(1, len(l)):\n",
    "                s = s + (2 * i - len(l)) * (l[i] - l[i - 1])\n",
    "                res[l[i]] = s\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        pos = defaultdict(list)\n",
    "        for i, v in enumerate(arr):\n",
    "            pos[v].append(i)\n",
    "        ans = [0] * len(arr)\n",
    "        for p in pos.values():\n",
    "            ans[p[0]] = s = sum(i - p[0] for i in p)\n",
    "            n = len(p)\n",
    "            for i in range(1, n):\n",
    "                s += (2 * i - n) * (p[i] - p[i - 1])\n",
    "                ans[p[i]] = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = [0] * n   \n",
    "        total = defaultdict(int)   \n",
    "        cnt = defaultdict(int) \n",
    "        for i in range(n):\n",
    "            val = arr[i]\n",
    "            if val in cnt:\n",
    "                res[i] += i * cnt[val] - total[val]\n",
    "            total[val] += i\n",
    "            cnt[val] += 1\n",
    "        total.clear()\n",
    "        cnt.clear()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            val = arr[i]\n",
    "            if val in cnt:\n",
    "                res[i] += total[val] - i * cnt[val] \n",
    "            total[val] += i\n",
    "            cnt[val] += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: list[int]) -> list[int]:\n",
    "        pos = defaultdict(list)\n",
    "        for i, v in enumerate(arr):\n",
    "            pos[v].append(i)\n",
    "        ans = [0] * len(arr)\n",
    "        for p in pos.values():\n",
    "            ans[p[0]] = s = sum(k - p[0] for k in p)\n",
    "            n = len(p)\n",
    "            for j in range(1, n):\n",
    "                s += (2 * j - n) * (p[j] - p[j-1])\n",
    "                ans[p[j]] = s\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        pos = defaultdict(list)\n",
    "        for i, v in enumerate(arr):\n",
    "            pos[v].append(i)  # 记录相同元素的位置\n",
    "        ans = [0] * len(arr)\n",
    "        for p in pos.values():  # 遍历每个组\n",
    "            ans[p[0]] = s = sum(i - p[0] for i in p)  # 该组第一个元素的间隔和\n",
    "            n = len(p)\n",
    "            for i in range(1, n):\n",
    "                s += (2 * i - n) * (p[i] - p[i - 1])  # 计算该组下一个元素的间隔和（考虑变化量）\n",
    "                ans[p[i]] = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        dic = defaultdict(list)\n",
    "        for i, x in enumerate(arr):\n",
    "            dic[x].append(i)\n",
    "        def set(num):\n",
    "            lst = dic[num]\n",
    "            print(lst)\n",
    "            left_cnt = left_sum = 0\n",
    "            right_cnt, right_sum = len(lst) - 1, sum(lst)\n",
    "            for idx in lst:\n",
    "                right_sum -= idx\n",
    "                arr[idx] = idx*left_cnt - left_sum + right_sum - idx*right_cnt\n",
    "                left_cnt+=1\n",
    "                right_cnt-=1\n",
    "                left_sum += idx\n",
    "        for num in dic:\n",
    "            set(num)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        pos = defaultdict(list)\n",
    "        for i, v in enumerate(arr):\n",
    "            pos[v].append(i)  # 记录相同元素的位置\n",
    "        ans = [0] * len(arr)\n",
    "        for p in pos.values():  # 遍历每个组\n",
    "            ans[p[0]] = s = sum(i - p[0] for i in p)  # 该组第一个元素的间隔和\n",
    "            n = len(p)\n",
    "            for i in range(1, n):\n",
    "                s += (2 * i - n) * (p[i] - p[i - 1])  # 计算该组下一个元素的间隔和（考虑变化量）\n",
    "                ans[p[i]] = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        pos = defaultdict(list)\n",
    "\n",
    "        for i, v in enumerate(arr):\n",
    "\n",
    "            pos[v].append(i)  # 记录相同元素的位置\n",
    "\n",
    "        ans = [0] * len(arr)\n",
    "\n",
    "        for p in pos.values():  # 遍历每个组\n",
    "\n",
    "            ans[p[0]] = s = sum(i - p[0] for i in p)  # 该组第一个元素的间隔和\n",
    "\n",
    "            n = len(p)\n",
    "\n",
    "            for i in range(1, n):\n",
    "\n",
    "                s += (2 * i - n) * (p[i] - p[i - 1])  # 计算该组下一个元素的间隔和（考虑变化量）\n",
    "\n",
    "                ans[p[i]] = s\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        pos = defaultdict(list)\n",
    "        for i, v in enumerate(arr):\n",
    "            pos[v].append(i)\n",
    "        ans = [0] * len(arr)\n",
    "        for p in pos.values():\n",
    "            ans[p[0]] = s = sum(i - p[0] for i in p)\n",
    "            n = len(p)\n",
    "            for i in range(1, n):\n",
    "                s += (2 * i - n) * (p[i] - p[i - 1])\n",
    "                ans[p[i]] = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        idx_list = defaultdict(list)\n",
    "        for i, a in enumerate(arr):\n",
    "            idx_list[a].append(i)\n",
    "        res = [0] * len(arr)\n",
    "        for v in idx_list.values():\n",
    "            s = res[v[0]] = sum(i-v[0] for i in v)\n",
    "            n = len(v)\n",
    "            for i in range(1, n):\n",
    "                s += (2*i-n) * (v[i]-v[i-1])\n",
    "                res[v[i]] = s\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        c = defaultdict(list)\n",
    "        for ii, jj in enumerate(arr):\n",
    "            c[jj].append(ii)\n",
    "        N = len(arr)\n",
    "        res = [0] * N\n",
    "        for ii, jj in c.items():\n",
    "            if len(jj) == 1:\n",
    "                continue\n",
    "            M = len(jj)\n",
    "            tmp = sum(jj) - jj[0] * M\n",
    "            res[jj[0]] = tmp\n",
    "            idx = 1\n",
    "            while idx < M:\n",
    "                tmp = tmp - (jj[idx] - jj[idx - 1]) * (M - 1 - idx) + (jj[idx] - jj[idx - 1]) * (idx - 1)\n",
    "                res[jj[idx]] = tmp\n",
    "                idx += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        res = [0] * len(arr)\n",
    "\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for i, a in enumerate(arr):\n",
    "            mp[a].append(i)\n",
    "        \n",
    "        for key in mp:\n",
    "            sum_ = sum(mp[key])\n",
    "\n",
    "            #[2, 5, 6]\n",
    "            left_idx_sum = 0\n",
    "            for i in range(len(mp[key])):\n",
    "                idx = mp[key][i]\n",
    "\n",
    "                res[idx] = i * idx  - left_idx_sum + sum_ - left_idx_sum - idx - idx * (len(mp[key]) - i - 1)\n",
    "                left_idx_sum += idx \n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = [0] * n\n",
    "        mp = {}\n",
    "        for i, num in enumerate(arr):\n",
    "            pre, j, cnt = mp.get(num, [0, -1, 0])\n",
    "            cur = pre + (i - j) * cnt\n",
    "            res[i] = cur\n",
    "            mp[num] = [cur, i, cnt + 1]\n",
    "        mp = {}\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            num = arr[i]\n",
    "            pre, j, cnt = mp.get(num, [0, -1, 0])\n",
    "            cur = pre + (j - i) * cnt\n",
    "            res[i] += cur\n",
    "            mp[num] = [cur, i, cnt + 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr) #4\n",
    "        ans = [0]*n\n",
    "        #arr:       [1,_,_,_,1,_,_,1,_,_,1,_,_]\n",
    "        #positions: [0,_,_,_,4,_,_,7,_,_,10,_,_]\n",
    "        #p:         [0,1,2,3]\n",
    "        #ans:       [21,_,_,_,13,_,_,13,_,_,21,_,_]\n",
    "        #△intervals = (2*i - n)*(p[i]-p[i-1]) \n",
    "        pos = defaultdict(list)\n",
    "        for i,v in enumerate(arr):\n",
    "            pos[v].append(i)\n",
    "        for p in pos.values():\n",
    "            m = len(p)\n",
    "            if m == 1:\n",
    "                ans[p[0]] = 0\n",
    "            else:\n",
    "                ans[p[0]] = sum(p[1:])-p[0]*(m-1)\n",
    "            s = ans[p[0]]\n",
    "            for i in range(1,m):\n",
    "                s += (2*i-m)*(p[i]-p[i-1])\n",
    "                ans[p[i]] = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        pos = defaultdict(list)\n",
    "        ans = [0] * len(arr)\n",
    "        for i, v in enumerate(arr):\n",
    "            pos[v].append(i)\n",
    "            ans[pos[v][0]] += i - pos[v][0]\n",
    "        for p in pos.values():\n",
    "            n = len(p)\n",
    "            for i in range(1, n):\n",
    "                ans[p[i]] = ans[p[i-1]] + (p[i] - p[i-1]) * (2 * i - n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        pos = defaultdict(list)\n",
    "        ans = [0]*len(arr)\n",
    "        for i,num in enumerate(arr):\n",
    "            pos[num].append(i)\n",
    "        for p in pos.values():\n",
    "            ans[p[0]] = s = sum(i-p[0] for i in p)\n",
    "            n =  len(p)\n",
    "            for i in range(1,n):\n",
    "                s -=  (n-2*i)*(p[i]-p[i-1])\n",
    "                ans[p[i]] = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        pos = defaultdict(list)\n",
    "        ans = [0]*len(arr)\n",
    "        for i,num in enumerate(arr):\n",
    "            pos[num].append(i)\n",
    "        for p in pos.values():\n",
    "            ans[p[0]] = sum(i-p[0] for i in p)\n",
    "            n =  len(p)\n",
    "            for i in range(1,n):\n",
    "                ans[p[i]] = ans[p[i-1]] - (n-2*i)*(p[i]-p[i-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        cnt = defaultdict(list)\n",
    "        n = len(arr)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            cnt[arr[i]].append(i)\n",
    "        for pos in cnt.values():\n",
    "            d0 = sum(x - pos[0] for x in pos)\n",
    "            ans[pos[0]] = d0\n",
    "            m = len(pos)\n",
    "            for i in range(1, m):\n",
    "                change = (2 * i - m) * (pos[i] - pos[i - 1])\n",
    "                d0 += change\n",
    "                ans[pos[i]] = d0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = [0] * n   # 每个元素与相同元素间隔之和\n",
    "        total = defaultdict(int)   # 每个数值出现下标之和\n",
    "        cnt = defaultdict(int)   # 每个数值出现次数\n",
    "        # 正向遍历并更新两个哈希表以及间隔之和数组\n",
    "        for i in range(n):\n",
    "            val = arr[i]\n",
    "            if val in cnt:\n",
    "                res[i] += i * cnt[val] - total[val]\n",
    "            total[val] += i\n",
    "            cnt[val] += 1\n",
    "        # 清空哈希表，反向遍历并更新两个哈希表以及间隔之和数组\n",
    "        total.clear()\n",
    "        cnt.clear()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            val = arr[i]\n",
    "            if val in cnt:\n",
    "                res[i] += total[val] - i * cnt[val] \n",
    "            total[val] += i\n",
    "            cnt[val] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        d = defaultdict(list)\n",
    "        for i, a in enumerate(arr):\n",
    "            d[a].append(i)\n",
    "        ans = [0] * len(arr)\n",
    "        for key, value in d.items():\n",
    "            s = 0\n",
    "            for i in range(len(value)):\n",
    "                s += value[i] - value[0]\n",
    "            ans[value[0]] = s\n",
    "            for i in range(1, len(value)):\n",
    "                cur = value[i] - value[i-1]\n",
    "                s = s + cur * (2 * i - len(value))\n",
    "                ans[value[i]] = s\n",
    "                prev = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        d=defaultdict(list)\n",
    "        for i in range(len(arr)):\n",
    "            d[arr[i]].append(i)\n",
    "        n=len(arr)\n",
    "        def check(s):\n",
    "            if len(s)==1:\n",
    "                ans[s[0]]=0\n",
    "                return \n",
    "            tot=sum(s)\n",
    "            p=len(s)\n",
    "            pre=0\n",
    "            for i in range(p):\n",
    "                ans[s[i]]=(tot-pre-s[i])-(p-i-1)*s[i]+(i)*s[i]-pre\n",
    "                pre+=s[i]\n",
    "\n",
    "            \n",
    "        ans=[0 for i in range(n)]\n",
    "        for i in d:\n",
    "            check(d[i])\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        pos = defaultdict(list)\n",
    "        for i in range(len(arr)):\n",
    "            pos[arr[i]].append(i)\n",
    "        ans = [0] * len(arr)\n",
    "        for a in pos.values():\n",
    "            n = len(a)\n",
    "            s = list(accumulate(a, initial=0))  # 前缀和\n",
    "            for j, target in enumerate(a):\n",
    "                left = target * j - s[j]\n",
    "                right = s[n] - s[j+1] - target * (n - j - 1)  # 绿色面积\n",
    "                ans[target] = left + right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(arr)\n",
    "        dct = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            dct[arr[i]].append(i)\n",
    "        ans = [0]*n\n",
    "        for num in dct:\n",
    "            lst = dct[num][:]\n",
    "            m = len(lst)\n",
    "            pre = list(accumulate(lst, initial=0))\n",
    "            for i in range(m):\n",
    "                x = lst[i]\n",
    "                ans[x] = (i+1)*x - pre[i+1] + (pre[-1]-pre[i+1]) - (m-i-1)*x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        d = {}\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in d:\n",
    "                d[arr[i]].append(i)\n",
    "            else:\n",
    "                d[arr[i]] = [i]\n",
    "        tmp = []\n",
    "        for k in d:\n",
    "            sum_ = 0\n",
    "            for i in range(1,len(d[k])):\n",
    "                sum_ += (d[k][i]-d[k][0])\n",
    "            tmp.append([d[k][0],sum_])\n",
    "            for i in range(1,len(d[k])):\n",
    "                left = i*abs(d[k][i]-d[k][i-1])\n",
    "                right = (len(d[k])-i)*abs(d[k][i]-d[k][i-1])\n",
    "                sum_ += (left-right)\n",
    "                tmp.append([d[k][i],sum_])\n",
    "        tmp.sort(key=lambda x : x[0])\n",
    "        res = []\n",
    "        for index,s in tmp:\n",
    "            res.append(s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistances(self, arr: List[int]) -> List[int]:\n",
    "        maxv = max(arr)\n",
    "        pos = [[] for _ in range(maxv + 1)]\n",
    "        n = len(arr)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            k = arr[i]\n",
    "            pl = pos[k]\n",
    "            if not pl:\n",
    "                pos[k] = [[i, 0]]\n",
    "            else:\n",
    "                last, lastsum = pl[-1]\n",
    "                pl.append([i, lastsum + i - last])\n",
    "        ret = [0] * n\n",
    "        for i in range(maxv + 1):\n",
    "            pl = pos[i]\n",
    "            if not pl:\n",
    "                continue\n",
    "            s = sum(x[1] for x in pl)\n",
    "            ret[pl[0][0]] = s\n",
    "            k = len(pl)\n",
    "            print(i, pl)\n",
    "            for i in range(1, k):\n",
    "                last, lastsum = pl[i]\n",
    "             \n",
    "                s += (2 * i - k) * (pl[i][1] - pl[i - 1][1])\n",
    "                ret[last] = s\n",
    "        return ret\n",
    "            \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
